package codingforgreat.lchot150;

public class Lc124 {
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public class Info{
        public int maxPathSum;
        public int maxPathSumFromHead;
        public Info(int max1,int max2){
            maxPathSum = max1;
            maxPathSumFromHead = max2;
        }
    }
    public int maxPathSum(TreeNode root) {
        return process(root).maxPathSum;
    }
    public Info process(TreeNode root){
        if(root == null){
            return null;
        }
        Info l = process(root.left);
        Info r = process(root.right);
        int maxPathSumFromHead = root.val;
        int  maxPathSum = root.val;
        if(l != null){
            maxPathSumFromHead = Math.max(maxPathSumFromHead,l.maxPathSumFromHead + root.val);
        }
        if(r != null){
            maxPathSumFromHead = Math.max(maxPathSumFromHead,r.maxPathSumFromHead + root.val);
        }
        if(l != null){
            maxPathSum = Math.max(maxPathSum,l.maxPathSum);
        }
        if(r != null){
            maxPathSum = Math.max(maxPathSum,r.maxPathSum);
        }
        if(l != null && r != null && l.maxPathSumFromHead > 0 && r.maxPathSumFromHead > 0){
            maxPathSum = Math.max(maxPathSum,l.maxPathSumFromHead + r.maxPathSumFromHead + root.val);
        }
        maxPathSum = Math.max(maxPathSum,maxPathSumFromHead);
        return new Info(maxPathSum,maxPathSumFromHead);
    }
}
